package Classic150;

import java.util.HashMap;
import java.util.Map;

public class LRU缓存 {
    /*
        即构造LinkedHashMap，双向链表加哈希表
     */
    class LRUCache {
        class DLinkedNode {
            int key;
            int value;
            DLinkedNode prev;
            DLinkedNode next;

            public DLinkedNode() {

            }

            public DLinkedNode(int _key, int _value) {
                key = _key;
                value = _value;
            }
        }

        private Map<Integer, DLinkedNode> map;
        private int capacity;
        private int size;
        private DLinkedNode head;
        private DLinkedNode tail;

        public LRUCache(int capacity) {
            map = new HashMap<>();
            this.capacity = capacity;
            size = 0;
            head = new DLinkedNode();
            tail = new DLinkedNode();
            head.next = tail;
            tail.prev = head;
        }

        public int get(int key) {
            DLinkedNode node = map.get(key);
            if (node != null) {
                move2Head(node);
                return node.value;
            }
            return -1;
        }

        public void put(int key, int value) {
            DLinkedNode node = map.get(key);
            if (node == null) {
                DLinkedNode newNode = new DLinkedNode(key, value);
                map.put(key, newNode);
                add2Head(newNode);
                if (++size > capacity) {
                    DLinkedNode tail = removeTail();
                    map.remove(tail.key);
                    size--;
                }
            }
            else {
                node.value = value;
                move2Head(node);
            }
        }

        private void add2Head(DLinkedNode node) {
            node.prev = head;
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
        }

        private void move2Head(DLinkedNode node) {
            removeNode(node);
            add2Head(node);
        }

        private DLinkedNode removeTail() {
            DLinkedNode oldTail = tail.prev;
            removeNode(oldTail);
            return oldTail;
        }

        private void removeNode(DLinkedNode node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    }
}
